package com.xushuda.yas.tmp;

import java.util.Random;

/**
 * Created by xushuda on 15/4/23.
 * store all the data node in memory structure
 */
@Deprecated
public class DataNodes{
    private int max_height;

    private DataNode head;

    private static Random ran = new Random();
    // a data node in the data nodes
    class DataNode {
        DataNode next[];
        DataNode prev[];
        String key;
        byte[] value;
        int height;
        DataNode(String key ,byte[] value){
            this.key = key;
            this.value = value;
            height = ran.nextInt()%max_height;
            next = new DataNode[height];
            prev = new DataNode[height];
        }
        DataNode(String key,byte[] value, int min_height){
            this.key = key;
            this.value = value;
            height = ran.nextInt()%(max_height-min_height)+min_height;
            next = new DataNode[height];
            prev = new DataNode[height];
        }
        public void insertAfter(DataNode node){
        }
    }

    public DataNodes(){

    }
   
    public byte[] search(String key){
        DataNode preNode = getPrevious(key);
        return null != preNode.next && 0 == preNode.next[0].key.compareTo(key) ?
                preNode.next[0].value : null;
    }

    public void insert(String key, byte[] value){

        if (null == head){
            // head max height
            head = new DataNode(key,value,max_height);
        }else{
            DataNode preNode = getPrevious(key);
            DataNode node = new DataNode(key, value, preNode.height);
            for(int i = 0; i<node.height;i++){

            }
        }
    }

    public void remove(){

    }

    private DataNode getPrevious(String key){
        // current 为小于key的最近元素
        DataNode current = head;
        if(null == head || 0 > key.compareTo(head.key)){
            return null;
        }
        // previous 为current的前继(当前层链表的前继)
        DataNode previous = null;
        // 外循环为从上到下遍历链表，内循环为从左到右遍历
        for (int i = max_height - 1; i >= 0; i--) {
            assert (null != current && 0 <= key.compareTo(current.key));
            if (0 == key.compareTo(current.key)) {// equals, return the previous
                return current.prev[0];
            } else if (0 < key.compareTo(current.key)) {// key >= current.key
                // 终止条件：当key比current.key小时，或没有后继，跳出循环，进入下一层链表
                while(0 < key.compareTo(current.key) && null != current.next[i]){// null != current.next[i] is important
                    previous = current;
                    current = current.next[i];
                }
                // key 比 current.KEY小，退回到前继
                if(0 > key.compareTo(current.key)){
                    current = previous;
                }
                // 最后一个元素，直接下降
            } else { // key < current.key
                //直接下降
            }
        }
        // 循环退出，没有找到key相等的值，并且也没有找到最后（KEY比所有元素都大），previous为最后一层的前继节点
        return previous;
    }
    // 获取搜索路径
    @SuppressWarnings("unused")
    private DataNode[] getSearchPath(String key){
        if(null == head || 0 > key.compareTo(head.key)){
            return null;
        }
        DataNode[] result = new DataNode[max_height];
        DataNode current = head;
        // previous 为current的前继(当前层链表的前继)
        DataNode previous = null;
        // 外循环为从上到下遍历链表，内循环为从左到右遍历
        for (int i = max_height - 1; i >= 0; i--) {
            assert (null != current && 0 <= key.compareTo(current.key));
            if (0 == key.compareTo(current.key)) {// equals, return the previous
                result[i] = current.prev[0];
            } else if (0 < key.compareTo(current.key)) {// key >= current.key
                // key比current.key小时，或没有后继，跳出循环，进入下一层链表
                while(0 < key.compareTo(current.key) && null != current.next[i]){// null != current.next[i] is important
                    previous = current;
                    current = current.next[i];
                }
                // 回退到前继,将会继续从前继节点开始，在下一层搜寻
                if(0 > key.compareTo(current.key)) {
                    current = previous;
                }
                result[i] = current;
            } else {
                assert (false);
            }
        }
        // 循环退出，
        return result;
    }
}

